package com.spirng.leetcode.uitl;

public class MaxHeap {
    int [] array;
    int size;
    public MaxHeap(int capacity){
        this.array=new int [capacity];
    }
    private void heapify(){
        for(int i=size/2-1;i>=0;i--){
            down(i);
        }
    }
    public int poll(){
        int top=array[0];
        swap(0,size-1);
        size--;
        down(0);
        return top;
    }
    public int poll(int index){
        int deleted=array[index];
        swap(index,size-1);
        size--;
        down(index);
        return deleted;
    }
    public void replace(int replaced){
        array[0]=replaced;
        down(0);
    }
    public int peek(){
        return 0;
    }
    public boolean offer(int offered){
        if(size== array.length){
            return false;
        }
        up(offered);
        size++;
        return true;
    }
    private void up(int offered){
        int child=size;
        while(child>0){
            int parent=(child-1)/2;
            if(offered>array[parent]){
                array[child]=array[parent];
            }else {
                break;
            }
            child=parent;
        }
    }
    private void down(int parent){
         int left=parent*2-1;
         int right=left+1;
         int max=parent;
         if(left<size&&array[left]>array[max]){
             max=left;
         }
         if(right<size&&array[right]>array[max]){
            max=right;
        }
         if(max!=parent){
             swap(parent, max);
             down(max);
         }
    }
    private void swap(int i,int j){
        int t=array[j];
        array[i]=array[j];
        array[j]=t;
    }
}
